# 纯质数
import math


def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(math.sqrt(n)) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    return {num for num, prime in enumerate(is_prime) if prime}


def count(num):
    primes_in_ten = sieve(10)
    primes = sieve(num)
    cnt = 0
    res = []
    for prime in primes:
        if prime < 10:
            cnt += 1
        else:
            temp = prime
            while prime % 10 in primes_in_ten:
                prime //= 10
            if prime == 0:
                cnt += 1
                res.append(temp)
    return cnt


if __name__ == '__main__':
    print(count(20210605))
